home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / exact.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  3.7 KB  |  167 lines  |  [TEXT/R*ch]
  1. #include "espresso.h"
  2.  
  3.  
  4. static void dump_irredundant();
  5. static pcover do_minimize();
  6.  
  7.  
  8. /*
  9.  *  minimize_exact -- main entry point for exact minimization
  10.  *
  11.  *  Global flags which affect this routine are:
  12.  *
  13.  *      debug
  14.  *      skip_make_sparse
  15.  */
  16.  
  17. pcover
  18. minimize_exact(F, D, R, exact_cover)
  19. pcover F, D, R;
  20. int exact_cover;
  21. {
  22.     return do_minimize(F, D, R, exact_cover, /*weighted*/ 0);
  23. }
  24.  
  25.  
  26. pcover
  27. minimize_exact_literals(F, D, R, exact_cover)
  28. pcover F, D, R;
  29. int exact_cover;
  30. {
  31.     return do_minimize(F, D, R, exact_cover, /*weighted*/ 1);
  32. }
  33.  
  34.  
  35.  
  36. static pcover
  37. do_minimize(F, D, R, exact_cover, weighted)
  38. pcover F, D, R;
  39. int exact_cover;
  40. int weighted;
  41. {
  42.     pcover newF, E, Rt, Rp;
  43.     pset p, last;
  44.     int heur, level, *weights;
  45.     sm_matrix *table;
  46.     sm_row *cover;
  47.     sm_element *pe;
  48.     int debug_save = debug;
  49.  
  50.     if (debug & EXACT) {
  51.     debug |= (IRRED | MINCOV);
  52.     }
  53. #if defined(sun) || defined(bsd4_2)            /* hack ... */
  54.     if (debug & MINCOV) {
  55.     setlinebuf(stdout);
  56.     }
  57. #endif
  58.     level = (debug & MINCOV) ? 4 : 0;
  59.     heur = ! exact_cover;
  60.  
  61.     /* Generate all prime implicants */
  62.     EXEC(F = primes_consensus(cube2list(F, D)), "PRIMES     ", F);
  63.  
  64.     /* Setup the prime implicant table */
  65.     EXEC(irred_split_cover(F, D, &E, &Rt, &Rp), "ESSENTIALS ", E);
  66.     EXEC(table = irred_derive_table(D, E, Rp),  "PI-TABLE   ", Rp);
  67.  
  68.     /* Solve either a weighted or nonweighted covering problem */
  69.     if (weighted) {
  70.     /* correct only for all 2-valued variables */
  71.     weights = ALLOC(int, F->count);
  72.     foreach_set(Rp, last, p) {
  73.         weights[SIZE(p)] = cube.size - set_ord(p);
  74.     }
  75.     } else {
  76.     weights = NIL(int);
  77.     }
  78.     EXEC(cover=sm_minimum_cover(table,weights,heur,level), "MINCOV     ", F);
  79.     if (weights != 0) {
  80.     FREE(weights);
  81.     }
  82.  
  83.     if (debug & EXACT) {
  84.     dump_irredundant(E, Rt, Rp, table);
  85.     }
  86.  
  87.     /* Form the result cover */
  88.     newF = new_cover(100);
  89.     foreach_set(E, last, p) {
  90.     newF = sf_addset(newF, p);
  91.     }
  92.     sm_foreach_row_element(cover, pe) {
  93.     newF = sf_addset(newF, GETSET(F, pe->col_num));
  94.     }
  95.  
  96.     free_cover(E);
  97.     free_cover(Rt);
  98.     free_cover(Rp);
  99.     sm_free(table);
  100.     sm_row_free(cover);
  101.     free_cover(F);
  102.  
  103.     /* Attempt to make the results more sparse */
  104.     debug &= ~ (IRRED | SHARP | MINCOV);
  105.     if (! skip_make_sparse && R != 0) {
  106.     newF = make_sparse(newF, D, R);
  107.     }
  108.  
  109.     debug = debug_save;
  110.     return newF;
  111. }
  112.  
  113. static void
  114. dump_irredundant(E, Rt, Rp, table)
  115. pcover E, Rt, Rp;
  116. sm_matrix *table;
  117. {
  118.     FILE *fp_pi_table, *fp_primes;
  119.     pPLA PLA;
  120.     pset last, p;
  121.     char *file;
  122.  
  123.     if (filename == 0 || strcmp(filename, "(stdin)") == 0) {
  124.     fp_pi_table = fp_primes = stdout;
  125.     } else {
  126.     file = ALLOC(char, strlen(filename)+20);
  127.     (void) sprintf(file, "%s.primes", filename);
  128.     if ((fp_primes = fopen(file, "w")) == NULL) {
  129.         fprintf(stderr, "espresso: Unable to open %s\n", file);
  130.         fp_primes = stdout;
  131.     }
  132.     (void) sprintf(file, "%s.pi", filename);
  133.     if ((fp_pi_table = fopen(file, "w")) == NULL) {
  134.         fprintf(stderr, "espresso: Unable to open %s\n", file);
  135.         fp_pi_table = stdout;
  136.     }
  137.     FREE(file);
  138.     }
  139.  
  140.     PLA = new_PLA();
  141.     PLA_labels(PLA);
  142.  
  143.     fpr_header(fp_primes, PLA, F_type);
  144.     free_PLA(PLA);
  145.  
  146.     (void) fprintf(fp_primes, "# Essential primes are\n");
  147.     foreach_set(E, last, p) {
  148.     (void) fprintf(fp_primes, "%s\n", pc1(p));
  149.     }
  150.     fprintf(fp_primes, "# Totally redundant primes are\n");
  151.     foreach_set(Rt, last, p) {
  152.     (void) fprintf(fp_primes, "%s\n", pc1(p));
  153.     }
  154.     fprintf(fp_primes, "# Partially redundant primes are\n");
  155.     foreach_set(Rp, last, p) {
  156.     (void) fprintf(fp_primes, "%s\n", pc1(p));
  157.     }
  158.     if (fp_primes != stdout) {
  159.     (void) fclose(fp_primes);
  160.     }
  161.     
  162.     sm_write(fp_pi_table, table);
  163.     if (fp_pi_table != stdout) {
  164.     (void) fclose(fp_pi_table);
  165.     }
  166. }
  167.